package com.lili.math;

/**
 * @Auther: 李 力
 * @Date: 2024/8/5
 * @Description: 数字 1 的个数
 * @version: 1.0
 */
public class LeetCode233 {
    /*
     * 时间复杂度: O(logn)
     * 空间复杂度: O(1)
     * */
    public static int countDigitOne(int n) {
        long mulk = 1;
        int ans = 0;
        for (int k = 0; n >= mulk; k++) {
            int a = (int) ((n / (mulk * 10)) * mulk);
            int b = (int) Math.min(Math.max(n % (mulk * 10) - mulk + 1, 0), mulk);
            ans = ans + a + b;
            mulk = mulk * 10;
        }
        return ans;
    }
}
